
// 会溢出，不能用qsort
// int cmp(const void *a, const void *b) {
//     return (*(int **)a)[1] - (*(int **)b)[1]; 
// }

void swap(int **a, int **b) {
    int *t = *a; *a = *b; *b = t;
}

//根据arr[i][1]排序, 可以注意不要传入二维数组
void quick_sort(int **arr, int l, int r) 
{
    if (l < r) {
        int i = l, j = r;
        int *temp = arr[i];
        while (i < j) {
            while (i < j && arr[j][1] >= temp[1]) j--; 
            swap(&arr[i], &arr[j]);
            while (i < j && arr[i][1] <= temp[1]) i++; 
            swap(&arr[i], &arr[j]);
        } 
        arr[i] = temp;
        quick_sort(arr, l, i-1);
        quick_sort(arr, i+1, r);
    }
}


int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    if (pointsSize == 0) return 0;
    quick_sort(points, 0, pointsSize-1);  
    // 右端排序，则第二个气球的右端一定大于第一个气球的右端
    // 只需再判断第一个气球的右端大于等于第二个气球的左端即可判断有交集

    int right = points[0][1];  
    int count = 1;
    for (int i = 1; i < pointsSize; i++) {
        if (right < points[i][0]) {  // 前面气球右端 < 后面气球的左端，不能一次引爆
            count++;
            right = points[i][1];      
        }
    }
    return count;
}